package com.ting.test.algorithms.array;

/**
 * Created by 雷霆 on 2020/4/28.
 * <p>
 * Description：
 */
public class SlidingWindowMax {

    public int[] maxSlidingWindow(int[] arr, int k) {
        if (null == arr) {
            return null;
        }
        int length = arr.length;
        if (length == 0 || length < k) {
            return null;
        }
        int[] result = new int[length - k+1];
        int max_value;
        int max_index;

        max_index = findMax(arr, 0, k - 1);
        max_value = arr[max_index];
        int index = 0;
        for (int i = k - 1; i < length; i++) {
            if (max_value <= arr[i]) {
                max_value = arr[i];
                max_index = i;
            } else if ((i - max_index) >= k) {
                max_index = findMax(arr, max_index + 1, i);
                max_value = arr[max_index];
            }
            result[index] = max_value;
            ++index;

        }
        return result;
    }


    public int findMax(int[] arr, int start, int end) {
        int max_value = arr[start];
        int max_index = start;
        for (int k = start; k <= end; k++) {
            if (max_value <= arr[k]) {
                max_index = k;
                max_value = arr[k];
            }
        }
        return max_index;
    }

    public static void main(String[] args) {
        SlidingWindowMax slidingWindowMax = new SlidingWindowMax();

        int[] arr = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int[] result = slidingWindowMax.maxSlidingWindow(arr, 3);
        for (int k : result) {
            System.out.println(k);
        }

    }
}
